//: [Previous](@previous)

/*:
 # 堆排序
 * 最好情况 O(nLogn))
 * 最坏情况 O(nLogn))
 * 平均时间复杂度 O(nLogn))
 * 空间复杂度 O(1)
 
 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列
 
 1. 创建一个堆 H[0……n-1]；
 2. 把堆首（最大值）和堆尾互换；
 3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
 4. 重复步骤 2，直到堆的尺寸为 1
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func heapSort(_ items: [Int]) -> [Int] {
    
    print("堆排序：\(items)")
    var list = items
    var endIndex = items.count - 1
    
    //创建大顶堆，其实就是将list转换成大顶堆层次的遍历结果
    heapCreate(items: &list)
    
    print("原始堆：\(list)")
    while endIndex >= 0 {
        //将大顶堆的顶点（最大的那个值）与大顶堆的最后一个值进行交换
        print("将list[0]:\(list[0])与list[\(endIndex)]:\(list[endIndex])交换")
        let temp = list[0]
        list[0] = list[endIndex]
        list[endIndex] = temp
        endIndex -= 1   //缩小大顶堆的范围
        
        //对交换后的大顶堆进行调整，使其重新成为大顶堆
        heapAdjast(items: &list, startIndex: 0,endIndex: endIndex + 1)
        print("调整后:\(list)\n")
    }
    return list
}


/// 构建大顶堆的层次遍历序列（f(i) > f(2i), f(i) > f(2i+1) i > 0）
///
/// - parameter items:    构建大顶堆的序列
func heapCreate(items: inout [Int]) {
    var i = items.count
    while i > 0 {
        heapAdjast(items: &items, startIndex: i - 1, endIndex:items.count)
        i -= 1
    }
}

/// 对大顶堆的局部进行调整，使其该节点的所有父类符合大顶堆的特点
///
/// - parameter items:    list
/// - parameter endIndex: 当前要调整的节点
func heapAdjast(items: inout [Int], startIndex: Int, endIndex: Int) {
    let temp = items[startIndex]
    var fatherIndex = startIndex + 1    //父节点下标
    var maxChildIndex = 2 * fatherIndex //左孩子下标
    
    while maxChildIndex <= endIndex {
        //比较左右孩子并找出比较大的下标
        if maxChildIndex < endIndex && items[maxChildIndex-1] < items[maxChildIndex] {
            maxChildIndex = maxChildIndex + 1
        }
        
        //如果较大的那个子节点比根节点大，就将该节点的值赋给父节点
        if temp < items[maxChildIndex-1] {
            items[fatherIndex-1] = items[maxChildIndex-1]
        } else {
            break
        }
        fatherIndex = maxChildIndex
        maxChildIndex = 2 * fatherIndex
    }
    items[fatherIndex-1] = temp
}

print("排序后 \(heapSort(numbers))")

//: [Next](@next)
